Добро пожаловать на Урок 3 курса Основы искусственного интеллекта (PolyU COMP5511). На этом занятии мы переходим от поиска пути для одного агента к поиску с противником, где агенты действуют в конкурентных многогаентных средах. Мы также знакомимся с задачами удовлетворения ограничений (CSP), — парадигмой, в которой цель состоит в поиске состояния, удовлетворяющего конкретному набору ограничений, а не пути.
Ключевые концепции
- Поиск с противником: Охватывает такие алгоритмы, как Минимакс и альфа-бета отсечение для принятия рациональных решений в игре против интеллектуального соперника.
- Монте-Карло поиск по дереву (MCTS): Исследует вероятностное принятие решений и лежит в основе современных игровых ИИ, таких как AlphaGo.
- Удовлетворение ограничений: Моделирует задачи с помощью переменных, областей определения и ограничений, решаемых методами поиска с возвратом и и локального поиска.
Анализ сложности
В условиях противоборства сложность пространства поиска часто определяется коэффициентом ветвления игры
Предупреждение о смене парадигмы
В отличие от стандартного поиска (например, A* или BFS), где среда статична, поиску с противником предполагает, что среда (соперник) активно стремится минимизировать ваш успех. В CSPпорядок действий менее важен, чем корректность итогового назначения.
Концептуальный псевдокод: типы агентов
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).